package com.leetcode.贪心;

import java.util.Arrays;

/**
 * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
 * 你需要按照以下要求，给这些孩子分发糖果：
 * 每个孩子至少分配到 1 个糖果
 * 相邻两个孩子评分更高的孩子会获得更多的糖果
 * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
 * @author LZF
 *
 */
public class L135分发糖果 {
	public static void main(String[] args) {
		int[] candy = new int[] {0,1,2,3,2,1};
		candy(candy);
	}
	/**
	 * 贪心：
	 * 
	 */
	public static int candy(int[] ratings) {
		/**
		 * 贪心解法、两遍贪心：
		 * 第一遍：从前往后遍历
		 * 局部最优：右边的孩子评分比左边高，那么右边的孩子的糖果就一定比左边多一个
		 * 得到的结果就是全局最优：相邻两个孩子之中， 处于右边评分高的孩子糖果都比左边多
		 * 
		 * 离满足题意还差一个条件：处于左边评分高的孩子，糖果还没有比右边多
		 * 因此，在第一遍贪心的基础之上，还要在进行一次贪心。
		 * 第二遍：
		 * 局部最优：左边的孩子评分比右边高，那么左边的孩子的糖果就一定比右边多，多多少呢？
		 * 	因为这个孩子i已经得到比他的左边i-1多的糖果数（第一遍贪心的结果），因此他在比i+1多的情况下，不能小于他此时比左边i-1多的糖果数
		 * 	因此，candy[i] = max(candy[i],candy[i+1] + 1),要取最大值，才能保证比左右两边都大
		 * 全局最优：相邻两个孩子之中， 处于左边评分高的孩子糖果都比右边多
		 * 
		 * 还有一个问题：第二遍贪心需要从前往后遍历，还是从后往前遍历？
		 * 从局部最优的分析可以看出：candy[i]受candy[i+1]的影响，如果先更新candy[i],后更新candy[i+1]（这是从前往后遍历），
		 * 有可能会使candy[i]的结果不准确，因为candy[i+1]的结果更新了
		 * 因此需要先更新candy[i+1],再更新candy[i]，那这就是从后往前遍历！！！！！这是需要注意的点。
		 * 
		 * 
		 */
		int[] candyVec = new int[ratings.length];
		Arrays.fill(candyVec, 1);
		//第一遍贪心，从前往后遍历，得到右边评分高的糖果比左边多
		for(int i = 1;i < ratings.length;i++) {
			if(ratings[i] > ratings[i - 1]) 
				candyVec[i] = candyVec[i - 1] + 1;
		}
		//第二百你贪心，从后往前遍历，得到左边评分高的糖果比右边多，同时满足第一次遍历的结果。
		for(int i = ratings.length - 2;i >= 0;i--) {
			if(ratings[i] > ratings[i + 1]) {
				candyVec[i] = Math.max(candyVec[i],candyVec[i + 1] + 1);
			}
		}
		int result = 0;
		//统计
		for(int i = 0;i < candyVec.length;i++)
			result += candyVec[i];
		return result;
		/**
		 * 暴力解法
		 */
//        
//        int minIndex = 0;
//        for(int i = 0;i < ratings.length;i++){
//            if(ratings[minIndex] > ratings[i]){
//                minIndex = i;
//            }
//        }
//        int[] candy = new int[ratings.length];
//        candy[minIndex] = 1;
//        int total = 0;
//        int i = minIndex - 1;
//        while(i >= 0){
//            if(ratings[i] > ratings[i + 1]){
//                candy[i] = candy[i + 1] + 1;
//            }  else if(ratings[i] == ratings[i + 1]){
//                candy[i] = 1;
//            }else {
//                if(candy[i + 1] == 1){
//                    candy[i] = 1;
//                    int j = i + 1;
//                    while(j < minIndex){
//                        if(ratings[j] > ratings[j - 1]){
//                        	if(candy[j] <= candy[j - 1])
//                        		candy[j] = candy[j - 1] + 1;
//                        }else{
//                            break;
//                        }
//                        j++;
//                    }
//                } else {
//                    candy[i] = 1;
//                }
//                
//            }
//            i--;
//        }
//        i = minIndex + 1;
//        while(i < ratings.length){
//            if(ratings[i] > ratings[i - 1]){
//                candy[i] = candy[i - 1] + 1;
//            } else if(ratings[i] == ratings[i - 1]){
//                candy[i] = 1;
//            }else{
//                if(candy[i - 1] == 1){
//                    candy[i] = 1;
//                    int j = i - 1;
//                    while(j > minIndex){
//                        if(ratings[j] > ratings[j + 1]){
//                        	if(candy[j] <= candy[j + 1])
//                        		candy[j] = candy[j + 1] + 1;
//                        }else{
//                            break;
//                        }
//                        j--;
//                    }
//                } else {
//                    candy[i] = 1;
//                }
//                
//            }
//            i++;
//        }
//        for(i = 0;i < candy.length;i++){
//            System.out.print(candy[i] + " ");
//            total += candy[i];
//        }
//        return total;
    }
}
